#include <stdio.h>

#include "bitree.h"

// 外部变量，用于记录最大深度
int maxDepth = 0;

// visit函数，用于更新最大深度
void visit(BiTree t, int currentDepth) {
    if (currentDepth > maxDepth) {
        maxDepth = currentDepth;
    }
}

// 通过遍历方式计算深度
void DepthTraverse(BiTree t, int currentDepth) {
    if (!t) {
        return;
    }
    
    // 访问当前节点，更新最大深度
    visit(t, currentDepth);
    
    // 递归遍历左右子树，深度加1
    DepthTraverse(t->lchild, currentDepth + 1);
    DepthTraverse(t->rchild, currentDepth + 1);
}

// 计算二叉树深度的主函数
int Depth(BiTree t) {
    maxDepth = 0;  // 重置最大深度
    if (!t) {
        return 0;
    }
    DepthTraverse(t, 1);  // 从深度1开始遍历
    return maxDepth;
}

void TestDepth(ElemType arr[], int n) {
    printf("test begin\n");

    BiTree root;
    LevelOrderCreateBiTree(&root, arr, n);
    printf("深度为：%d\n", Depth(root));

    printf("test end\n");
}

int main() {
    ElemType arr1[] = {'A'};
    TestDepth(arr1, 1);

    ElemType arr2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    TestDepth(arr2, 7);

    ElemType arr3[] = {'A', 'B', 'C', '#', '#', 'D', 'E', '#',
                       'F', '#', '#', 'G', '#', '#', '#'};
    TestDepth(arr3, 15);

    return 0;
}